<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0136)http://pcwi1060.uni-muenster.de/ceoi2003/contest/main.php?page=showtask&taskid=square&print=1&sessionid=e32f546c67bd7ea7cce7fdd451f4ba3b --><?xml version="1.0" encoding="iso-8859-1"?><HTML 
lang=en xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"><HEAD><TITLE>CEOI 2003 - Contest Environment</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312"><LINK 
href="CEOI 2003 - Contest Environment.files/style.css" type=text/css 
rel=stylesheet>
<META content="MSHTML 6.00.2716.2200" name=GENERATOR></HEAD>
<BODY><!-- Begin pagecontent -->
<H2>Square</H2>
<P>You are given a graph. All vertices are positioned on a NxN grid of points (1 
�� N �� 2003). Each point is occupied by exactly one vertex. Each vertex has 
directed edges to its neighbor vertices to the right and to the bottom, if they 
exist. These edges are weighted with an integer w (1 �� w �� 500&nbsp;000). Every 
path starting at the upper left vertex (at v<SUB>1,1</SUB>) to a vertex 
v<SUB>x,y</SUB> has the same weight. The weight of a path is the sum of the 
weight of the edges along the path. </P>
<P>In the following graph with N=3, every path from vertex v<SUB>1,1</SUB> to 
v<SUB>2,2</SUB> has weight 4. The only path from v<SUB>1,1</SUB> to 
v<SUB>1,2</SUB> has weight 2. </P>
<P><center><IMG height=204 alt="square example" src="0185.gif" width=209></center></P>
<P>You are given an integer L (1�� L�� 2&nbsp;000&nbsp;000&nbsp;000). Your task is 
to search for a vertex v<SUB>x,y</SUB> so that a path from v<SUB>1,1</SUB> to 
v<SUB>x,y</SUB> have exactly weight L. The weights are not directly given to 
your program, and so it has to ask for a special weight by using a library. Your 
program is only allowed to ask for at most 6667 weights. </P>
<P>The library offers the following functions: <TT>getN()</TT> and 
<TT>getL()</TT> return the values for N and L. <TT>getWeight(x, y, 
direction)</TT> returns the weight of the edge starting at v<SUB>x,y</SUB> to 
the right (<TT>direction=0</TT>) or to the bottom (<TT>direction=1</TT>). </P>
<P>If you have found a vertex v<SUB>x,y</SUB> so that a path from 
v<SUB>1,1</SUB> to v<SUB>x,y</SUB> has exactly weight L, you have to call 
<TT>solution(x, y)</TT>. If no such vertex exists, call <TT>solution(-1, 
-1)</TT>. Your program will be terminated automatically after calling 
<TT>solution(x, y)</TT>. If you perform more then 6667 calls to 
<TT>getWeight()</TT> or your solution is incorrect, you will get no points for 
that testcase. </P>
<P>This task has neither input nor output files. </P>
<H3>Library Functions</H3>
<TABLE cellPadding=3 border=1>
  <TBODY>
  <TR>
    <TD><B><TT>C/C++</TT></B></TD></TR>
  <TR>
    <TD>int getN(void)</TD></TR>
  <TR>
    <TD>int getL(void)</TD></TR>
  <TR>
    <TD>int getWeight(int x, int y, int direction)</TD></TR>
  <TR>
    <TD>void solution(int x, int y)</TD></TR>
  <TR>
    <TD><B><TT>Pascal</TT></B></TD></TR>
  <TR>
    <TD><TT>function getN: Longint</TT></TD></TR>
  <TR>
    <TD><TT>function getL: Longint</TT></TD></TR>
  <TR>
    <TD>function getWeight(x, y, direction: Longint): Longint</TT></TD></TR>
  <TR>
    <TD>procedure solution(x, y: Longint)</TD></TR></TBODY></TABLE>
<P>You can find a sample implementation of the library in <TT>/ceoi</TT> or 
<TT>c:\ceoi</TT>, but your program will be evaluated with another 
implementation. (For download: <A 
href="http://pcwi1060.uni-muenster.de/ceoi2003/contest/tasks/square_lib.h">square_lib.h</A> 
and <A 
href="http://pcwi1060.uni-muenster.de/ceoi2003/contest/tasks/square_lib.pas">square_lib.pas</A>. 
</P>
<P>For testing and debugging you can create the file <TT>square.in</TT>, which 
will be read by the sample library. The first line of <TT>square.in</TT> must 
contain the integers N and L. Each of the following N&nbsp;lines contains 
exactly N-1&nbsp;integers, the weights of the horizontal edges. After that, the 
following N-1&nbsp;lines contain N&nbsp;integers, the weights of the vertical 
edges. </P>
<P>The library is to be included via <TT>#include "square_lib.h"</TT> or 
<TT>uses square_lib</TT>. </P>
<P>Please note that the sample library you can use for testing is rather slow 
and memory consuming. This is because it has to read your input file into 
memory. Nevertheless you can assume that the evaluation library doesn't need any 
memory or running time at all. </P>
<H3>Example</H3>
<TABLE cellPadding=3 border=1>
  <TBODY>
  <TR>
    <TD><TT>square.in</TT></TD>
    <TD vAlign=top align=left width=198><TT>Protocol</TT></TD></TD></TR>
  <TR>
    <TD vAlign=top align=left><TT>3 4<BR>1 2<BR>2 3<BR>1 1<BR>2 3 4<BR>5 4 
      2</TT> </TD>
    <TD vAlign=top align=left width=198><TT>getN() -&gt; 3<BR>getL() -&gt; 
      4<BR>getWeight(1,1,0) -&gt; 1<BR>getWeight(2,1,1) -&gt; 3<BR>solution(2,2) 
      </TT></TD></TR></TBODY></TABLE>
<H4>Program name:</H4><B>square.pas</B> or <B>square.c</B> or 
<B>square.cpp</B><BR>
<H4>Time limit:</H4>1 second per test case 
</BODY></HTML>
